package 中等.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
 * 如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
 * 从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
 * 子数组 是数组中一个连续且可能为空的元素序列。
 */
public class 找出最长等值子数组_2831 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口
     * 1，最后子数组一定是 nums 里面的某个元素，可以选择枚举答案
     * ，枚举答案可以将相同数字的索引分组
     * 2，最多删除 k 个元素，可以认为窗口中只能有 k 个和目标元素
     * 不能的元素
     */
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int ans = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> list = map.get(nums.get(i));
            if (list == null) {
                list = new ArrayList<>();
                map.put(nums.get(i), list);
            }
            list.add(i);
        }

        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            int left = 0, curDiff = 0;
            for (int right = 0; right < list.size(); right++) {
                while (curDiff > k && left < right) {
                    curDiff -= list.get(left + 1) - list.get(left) - 1;
                    left++;
                }
                ans = Math.max(ans, list.get(right) - list.get(left) + 1 - curDiff);

                if (right < list.size() - 1) {
                    curDiff += list.get(right + 1) - list.get(right) - 1;
                }
            }
        }

        return ans;
    }

}
